Tên gọi "Cebu" bắt nguồn từ tiếng Cebu cổ là sibu hay sibo ("buôn bán"), một dạng tắt của sinibuayng hingpit ("nơi buôn bán"). Ban đầu nó được dùng cho bến cảng của thị trấn Sugbu, tên cổ của thành phố Cebu.[2] Từ thế kỷ 13 đến thế kỷ 16, các thương nhân từng dịch tên thành phố là Sebu, Sibuy, Zubu, hay Zebu, và các tên khác.[3] Sugbu bắt nguồn từ thuật ngữ tiếng Cebu cổ nghĩa là "tiêu thổ" hay "cháy lớn".[2][4]

Vương quốc Cebu bản địa tồn tại trên đảo trước khi người Tây Ban Nha đến. Vương quốc do Sri Lumay hay còn gọi là Rajamuda Lumaya lập nên, ông là một hoàng tử lai Mã Lai-Tamil của Vương triều Chola từng xâm chiếm Sumatra tại Indonesia. Ông được Maharajah cử đi lập một căn cứ cho lực lượng viễn chinh nhằm khuất phục các vương quốc bản địa, song ông lại làm phản và lập một vương quốc độc lập cho mình.[5]

Nhà thám hiểm người Bồ Đào Nha Ferdinand Magellan đến Cebu vào năm 1521, bắt đầu thời kỳ người Tây Ban Nha khám phá và thuộc địa hoá Philippines.[6][7] Khi đến thành phố Cebu, Magellan kết bạn với Quốc vương Cebu Rajah Humabon, và thuyết phục người bản địa liên minh với Tây Ban Nha. Magellan sau đó biết về quốc vương tại đảo Mactan lân cận là Datu Lapu-Lapu, vốn đối địch với Cebu và hai bên được cho là tranh giành quyền kiểm soát mậu dịch trong khu vực. Đến tháng 4, trận Mactan diễn ra, kết quả là người Tây Ban Nha bị đánh bại và Magellan bị người Mactan giết[8].

Năm 1564, các nhà thám hiểm Tây Ban Nha dưới quyền Miguel López de Legazpi đi từ Mexico và đến Cebu vào năm 1565, và lập ra một thuộc địa.[9] Người Tây Ban Nha chiến đấu với Quốc vương Rajah Tupas và chiếm lĩnh được lãnh thổ của ông. Người Tây Ban Nha lập ra các khu định cư, và hoạt động mậu dịch trở nên phát đạt. Cebu là khu định cư châu Âu đầu tiên do các nhà chinh phục Tây Ban Nha lập ra tại Philippines. Năm 1595, Đại học San Carlos được thành lập và đến năm 1860, Cebu mở cửa các cảng biển cho ngoại thương. Năm 1898, Philippines được Tây Ban Nha được nhượng cho Hoa Kỳ sau Chiến tranh Tây Ban Nha–Mỹ và Chiến tranh Hoa Kỳ-Philippines. Đến năm 1937, Cebu được các chính trị gia Philippines cai quản một cách độc lập.

Cebu giữ vai trò là một căn cứ của Nhật Bản trong thời gian họ chiếm đóng Philippines trong Chiến tranh thế giới thứ hai. Các hoạt động kháng Nhật diễn ra tại Cebu từ tháng 4 năm 1942 cho đến khi kết thúc chiến tranh. Tháng 3 năm 1945, liên quân Philippines và Hoa Kỳ đổ bộ và tái chiếm Cebu trong chiến dịch giải phóng Philippines.